\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}

\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Домашнее задание 4}

\paragraph{Задание 1.} Выразите хроматический многочлен графа через хроматические многочлены его компонент связности.

\begin{Solution}
Расскараска каждой компаненты связности не накладывает никаких ограничений на раскраску других компонент связности, следовательно, каждую компоненту связности можно красить независимо.

Пусть граф $G$ распадается на $n$ компонент связности $G_i$, тогда хроматический многочлен для всего графа равен:
\[
	P\left(G,t\right) = \prod_{i=1}^{n} P\left(G_i,t\right)
\]
\end{Solution}

\paragraph{Задание 2.} Найдите хроматический многочлен цикла на $n$ вершинах.

\begin{Solution}
Воспользуемся рекуррентной формулой:
\[
	P\left(G,t\right) = P\left(G-\left(u,v\right), t\right) - P\left(G \setminus \left(u,v\right), t\right)
\]
где $u,v$ - пара смежных вершин, $G-\left(u,v\right)$ - граф без ребра $\left(u,v\right)$, $G \setminus \left(u,v\right)$ - граф, после стягивания ребра $\left(u,v\right)$.

Выберем пару смежных вершин $u$ и $v$, удалим из $C_n$ связывающее их ребро и получем путь на $n$ вершинах, причем:
\[
	P\left(G-\left(u,v\right)\right) = t \left(t-1\right)^{n-1}
\]
Теперь объединим $u$ и $v$ в одну вершину и получим цикл на $n-1$ вершине, таким образом имеем:
\[
	P\left(C_n,t\right) = t\left(t-1\right)^{n-1} - P\left(C_{n-1}, t\right)
\]
рассмотрим граничные условия, для $P\left(C_n,t\right)$, очевидно, что для $n=3$, получаем $t \cdot \left(t-1\right) \cdot \left(t-2\right) = t \left[\left(t-1\right)^2 - \left(t-1\right)\right] = \left[t \pm 1\right]\left[\left(t-1\right)^2 - \left(t-1\right)\right] = \left[\left(t-1\right)^3 - \left(t-1\right)^2\right]+\left[\left(t-1\right)^2 - \left(t-1\right)\right] = \left(t-1\right)^3 - \left(t-1\right)$

Теперь идем от обратного, выразим хроматический многочлен цикла на 4 вершинах:
\[
	P\left(C_4,t\right) = t\left(t-1\right)^{3} - \left(t-1\right)^3 + \left(t-1\right) = \left(t-1\right)^4 + \left(t-1\right)
\]
далее для $C_5$:
\[
	P\left(C_5,t\right) = t\left(t-1\right)^4 - \left(t-1\right)^4 - \left(t-1\right) = \left(t-1\right)^5 - \left(t-1\right)
\]
Теперь положим, что
\[
	P\left(C_n,t\right) = \left(t-1\right)^n + \left(-1\right)^n \left(t-1\right)
\]
выведем для $C_{n+1}$:
\[
	P\left(C_{n+1},t\right) = t \left(t-1\right)^n - \left(t-1\right)^n - \left(-1\right)^n \left(t-1\right) = \left(t-1\right)^{n+1} - \left(-1\right)^n \left(t-1\right) = \left(t-1\right)^{n+1} + \left(-1\right)^{n+1} \left(t-1\right) 
\]
\end{Solution}

\paragraph{Задание 3.} В связном графе степень каждой вершины равна 5 и он остается связным при удалении любых трех ребер. Докажите, что в нем есть совершенное паросочетание.

\begin{Solution}
Пусть в графе существует запрещающее множество мощности $s$, т. е. существует как минимум $s+1$ компонента графа соединенная только с вершинами из $s$, мощность которой нечетна.

Рассмотрим четность числа ребер ведущих из нечетной компоненты в запрещающее множество. Пусть в компоненте $2k+1$ вершина, из компоненты в запрещающее множество ведет $m$ ребер, тогда
\[
	\left(\left(2k+1\right)\cdot 5 - m\right) \vdots 2
\]
Но это возможно только в случае, если $m$ - нечетно, а наименьшее нечетное число большее 3 есть 5. Следовательно из $s+1$ компоненты в запрещающее множество ведет как минимум $5 \left(s+1\right)$ ребер, что не возможно, так как в запреающем множестве всего $s$ вершин, следовательно, запрещающего множества не существует, следовательно, по теореме Татта, в графе существует совершенное паросочетание.
\end{Solution}

\paragraph{Задание 4.} Докажите, что если $G$ - (не обязательно связный) граф с $m$ блоками без изолированных вершин, то число 1 является корнем хроматического многочлена $P\left(G, t\right)$ кратности
\begin{itemize}
\item (a) не менее чем $m$

\item (b) ровно $m$
\end{itemize}

\begin{Solution}
Во-первых, очевидно что блок нельзя окрасить 1 цветом правильно, поэтому 1 является корнем хроматического многочлена блока.

Во-вторых, хроматический многочлен любого графа имеет своим корнем 0, следовательно содрежит множитель $t$ (или, например, при раскраске графа, первой раскрашиваемой вершине можно придать любой из $t$ цветов).

Наконец рассматриваем только связные графы, так как согласно задаче 1, если условие выполняется для каждой компоненты графа, то оно выполняется и для всего графа.

Пусть два блока графа пересекаются по общей вершине $v$. Обозначим хроматический многочлен первого блока как $t \left(t-1\right) P_1\left(t\right)$, а хроматический многочлен второго блока как $t \left(t-1\right) P_2\left(t\right)$, тогда хроматический многочлен их пересечения:
\[
	P\left(t\right) = t \left(t-1\right)^2 P_1\left(t\right) P_2\left(t\right)
\]
то есть за исключением окраски $v$ во всем остальном раскраска блоков незаивсима.

Пусть теперь два блока соединены ребром (ребро-мост, на самом деле тоже блок), тогда по рекуррентной формуле получаем, что:
\[
	P\left(t\right) = t^2\left(t-1\right)^2P_1\left(t\right) P_2\left(t\right) - t \left(t-1\right)^2 P_1\left(t\right) P_2\left(t\right)
\]
т. е. кратность $t-1$ равна 3, аналогичные утвердения справедливы и при соединении двух объединений блока, т. е. кратность 1 в хроматическом многочлене как минимум не меньше количества блоков.
\end{Solution}

\paragraph{Задание 5.} Докажите, что если вершины графа имеют степень не больше, чем $k$, то его вершины можно покрасить в $\left[k/2\right]+1$ цвет так, чтобы у каждой вершины было не более одного соседа того же цвета.

\begin{Solution}
Пронумеруем вершины графа в произвольном порядке. Будем красить вершины согласно нумерации в $\left[k/2\right] + 1$ цветов, так что бы цвета не пересекались с покрашенными соседями, при этом при окрашивании вершины покрасим и минимального непокрашенного соседа в тот же цвет.

Теперь допустим что, в какой-то момент на вершине $u$ все цвета оказались заняты
\end{Solution}

\paragraph{Задание 6.} Докажите, что у любого графа $G$ есть подграф, с минимальной степенью $\chi \left(G\right) - 1$

\begin{Solution}
Будем удалять из графа ребра, пока сохраняется его хроматическое число. Оставшийся граф представляет из себя набор компонент связности, причем как минимум у одной из них (на самом деле ровно у одной) хроматическое число совпадает с хроматическим числом графа, обозначим эту компоненту как $K$.

Пусть теперь в компоненте $K$ есть вершина $u$ степени меньшей $\chi \left(K\right) - 1$. Тогда $u$ имеет как минимум 2 допустимых цвета при любой окраске, но это значит, что она не влияет на хроматическое число $K$, так как не накладывает ограничений на оставшиеся вершины, следовательно удаление ребер не изменит хроматическое число, получаем противоречие, следовательно все вершины имееют как минимум степень $\chi \left(K\right) - 1 = \chi \left(G\right) - 1$, кроме того $K \subset G$, а значит искомая компонента.
\end{Solution}

\paragraph{Задание 7.} Докажите, что в каждом турнире либо вершины можно пронумеровать так, что стрелка всегда ведет от большего к меньшему, либо найдется треугольник, ориентированный по циклу.

\begin{Solution}
В одну сторону, если в графе не содержится циклов (в частности треугольника), то граф топологически сортируем, следовательно, вершины могут быть пронумерованы нужным образом.

В обратную сторону. Предположим противное, в графе нет цикла-треугольника и нельзя пронумеровать вершины нужным образом. Выделим в графе гамильтонов путь (в турнире он всегда существует) $v_1, v_2, v_3, ..., v_n$. Рассмотрим вершину $v_1$, в графе ребро $(v_1,v_2)$ ориентировано от $v_1$ к $v_2$, в противном случае в графе есть цикл-треугольник. Далее, пусть все ребра из $v_1$ в вершины $v_i$ ориентированы от $v_1$, тогда ребро в вершину $v_{i+1}$ также ориентированно от $v_1$, так как в противном случае $v_1, v_i, v_{i+1}$ - цикл-треугольник.

Пусть теперь условие теоремы справедливо для всех вершин с номерами меньше $i$, тогда рассуждения, подобные рассуждениям для $v_1$, справедливы и для $v_i$, но в данном случае не требуется рассматривать вершины с меньшими номерами, так как по индукционному предположению ребра для них ориентированны правильно.
\end{Solution}

\paragraph{Задание 8.} Найдите хроматический многочлен полного графа без одноого ребра.

\begin{Solution}
Обозначим полный граф без одного ребра как $G$. Рассмтоим полный граф и воспользуемся рекурсивной формулой для хроматического многочлена по отсутствующему ребру:
\[
	P\left(K_n,t\right) = P\left(G, t\right) - P\left(K_{n-1},t\right)
\]
следовательно:
\[
	P\left(G, t\right) = P\left(K_n,t\right) + P\left(K_{n-1},t\right)
\]
Хроматический многочлен полного графа найти просто:
\[
	P\left(K_n,t\right) = \prod_{i=0}^{n-1} \left(t-i\right)
\]
Тогда:
\[
	P\left(G, t\right) = \prod_{i=0}^{n-1} \left(t-i\right) + \prod_{i=0}^n \left(t-i\right) = \left(t-n+1\right) \prod_{i=0}^{n-1} \left(t-i\right)
\]
\end{Solution}

\paragraph{Задание 9.} Докажите, что хроматический многочлен графа $G$ на $n$ вершинах имеет вид $P\left(G,t\right) = x^n - a_{n-1} x^{n-1} + a_{n-2} x^{n-2} - ... + \left(-1\right)^n a_0$, где $a_i \ge 0$

\begin{Solution}
Сначала докажем, что старший коэффициент хроматического многочлена равен 1. Для графа $G$ имеем:
\[
	P\left(G,t\right) = P\left(G+\left(u,v\right),t\right) + P\left(G \setminus \left(u,v\right), t\right)
\]

Где $\left(u,v\right)$ - отсутствующее в $G$ ребро, а $G \setminus \left(u,v\right)$ - граф полученный из $G$ стягивание несмежных вершин $u$ и $v$ в одну. Применяя формулу рекурсивно добавляя отсутствующие ребра или стягивая несмежные вршины придем к полным графам, причем граф $K_n$ появится только один раз (в ветке с добавлением ребер), коэффициент $P\left(K_n, t\right)$ при $t^n$ равен 1, все хроматические многочлены остальных полных графов полученные в выражении будут иметь степень меньшую $n$, следовательно в сумме многочленов при $t^n$ имеем коэффициент 1.

Теперь покажем, что коэффициенты хроматического многочлена знакопеременны. Доказываем по индукции, база индукции граф точка, для которого все очевидно. Примем, что для любого графа на $n$ вершинах условие справедливо, добавим графу 1 вершину. Теперь делаем индукцию по числу ребер, для графа без ребер все очевидно, пусть теперь условие справедливо для $\left(n+1,m\right)$ графа $G$, покажем, что условие справедливо и для $\left(n+1,m+1\right)$ графа $G_1$, пусть добавленное ребро $\left(u,v\right)$. Обозначим за $G_2$ граф полученный из $G_1$ стягиванием ребра $\left(u,v\right)$, тогда справедлива формула:
\[
	P\left(G_1, t\right) = P\left(G,t\right) - P\left(G_2, t\right)
\]
по индукционному предположению теорема верна для $G$ и $G_2$, пусть теперь:
\[
	\begin{split}
		& P\left(G,t\right) = t^{n+1} - a_1 t^{n} + a_2 t^{n-1} - ... \\
		& P\left(G_2,t\right) = t^n - b_1 t^{n-1} + b_2 t^{n-2} - ...
	\end{split}
\]
тогда для разности многочленов имеем:
\[
	P\left(G_1, t\right) = t^{n+1} - \left(a_1 - 1\right) t^n + \left(a_2 + b_1\right) t^{n-1} - \left(a_3 + b_2\right) t^{n-2} + ...
\]
\end{Solution}
\end{document}
